package com.xw.class05;

/**
 * @author: xw
 * @create: 2022/9/27 14:57
 * @description:给你一个整数数组 nums 以及两个整数 lower 和 upper 。
 *                      求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。
 *                      输入：nums = [-2,5,-1], lower = -2, upper = 2
 *                      输出：3
 *                      解释：存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和分别是：-2 、-1 、2 。
 *                      思路：将数组转化为前置和数组，然后进行递归和merge
 */
public class Code01_CountOfRangeSum {

    public static int countRangeSum(int[] nums, int lower, int upper) {
        if(null == nums || nums.length==0) {
            return 0;
        }
        long[] sums = new long[nums.length];
        sums[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sums[i] = sums[i-1] + nums[i];
        }
        return process(sums, 0, sums.length - 1, lower, upper);
    }

    private static int process(long[] sums, int left, int right, int lower, int upper) {
        if (left == right) {
            return  sums[left] >= lower && sums[left] <= upper ? 1 : 0;
        }
        int mid = left + ((right-left)>>1);
        return process(sums,left,mid,lower,upper) +
                process(sums,mid+1,right,lower,upper) +
                merge(sums,left,mid,right,lower,upper);
    }


    private static int merge(long[] sums, int left, int mid, int right, int lower, int upper) {
        int ans = 0;
        int windowL = left;
        int windowR = left;
        for (int i = mid+1; i <= right ; i++) {
            long max = sums[i] - lower;
            long min = sums[i] -upper;
            while (windowR <= mid && sums[windowR] <= max){
                windowR++;
            }
            while(windowL <= mid && sums[windowL] < min){
                windowL++;
            }
//            ans += Math.max(0,windowR - windowL );
            ans += windowR - windowL ;
        }

        long[] help = new long[right-left +1];
        int i = 0;
        int p1 = left;
        int p2 = mid+1;
        while(p1 <= mid && p2 <= right){
            help[i++] = sums[p1] <= sums[p2] ? sums[p1++] : sums[p2++];
        }
        while (p1 <= mid){
            help[i++] = sums[p1++];
        }
        while (p2 <= right){
            help[i++] = sums[p2++];
        }
        for (i = 0; i < help.length; i++) {
            sums[left + i] = help[i];
        }
        return ans;
    }
}
